package nowCoder;


/**
 * 网易有道：
 * 将原来链表1，2，3，4重排为1，4，2，3
 * @author Ghost
 *
 */
class Nodee{
	public int element;
	public Nodee next;
	public Nodee(int a) {
		element = a;
		next = null;
	}
}
public class ReRank {
	Nodee reverse(Nodee head){
		if(head==null)
			return head;
		Nodee preNodee = null;
		Nodee current = head;
		Nodee next = current.next;
		current.next = preNodee;
		while(next!=null){
			preNodee = current;
			current = next;
			next = next.next;
			current.next = preNodee;
		}
		return current;
	}
	Nodee reRank(Nodee head){
		Nodee fast=head,slow=head;
		Nodee preSlow = null,head2 = null;
		while(fast.next!=null){
			preSlow = slow;
			slow = slow.next;
			fast = fast.next;
			if(fast.next!=null)
				fast = fast.next;
			else {
				head2 = slow;
				preSlow.next = null;
			}
		}
		
		if(head2==null){
			head2 = slow.next;
			slow.next = null;
		}
	    head2 = reverse(head2);
	    Nodee tmpNodee;
	    Nodee current = head;
		while(head2!=null){
			tmpNodee = head2;
			head2 = head2.next;
			tmpNodee.next = current.next;
			current.next = tmpNodee;
			current = current.next.next;
		}
		return head;
	}
	
	public static void main(String[] args){
		ReRank reRank = new ReRank();
		Nodee head = new Nodee(1);
		//head.next = new Nodee(2);
		//head.next.next=  new Nodee(3);
		//head.next.next.next = new Nodee(4);
		//head.next.next.next.next = new Nodee(5);
		Nodee nHeadNodee = reRank.reRank(head);
		while(nHeadNodee!=null){
			System.out.println(nHeadNodee.element);
			nHeadNodee = nHeadNodee.next;
		}
			
	}
}
